#include<bits/stdc++.h>
using namespace std;
int main(){
    int x,mod;
    cin>>x>>mod;
    set<int> se;
    int res = 1;
    for(int i = 1;i < mod;i++){
        res = 1ll*res*x%mod;
        se.insert(res);
    }
    cout<<se.size()<<'\n';
}